package leetcode100

// TODO 双指针 | 哑结点 【-】 删除链表的倒数第 N 个结点
// TODO https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	first, second := head, dummy
	// first 先向前行走 n 个节点
	for i := 0; i < n; i++ {
		first = first.Next
	}
	// first 和 second 同时行走, 直到 first 指到链表结尾
	for ; first != nil; first = first.Next {
		second = second.Next
	}
	second.Next = second.Next.Next
	return dummy.Next
}
